package mytest;

public class Kmp {

	/**
	 * 获得next数组；改进版
	 * @param str
	 * @return
	 */
	static int[] getNext(String str)
	{
		int next[]=new int[str.length()];
		
		next[0]=-1;
		int i=0,j=-1;
		while(i<str.length()-1)
		{
			if(j==-1||str.charAt(i)==str.charAt(j))
			{
				i++;
				j++;
				if(str.charAt(i)==str.charAt(j))
				{
					next[i]=next[j];
				}else {
					next[i]=j;
				}
			}else {
				j=next[j];
			}
		}
		
		return next;
	}
	
	
	/**
	 * kmp模式匹配算法
	 * @param S
	 * @param T
	 * @return
	 */
	static int kmp(String S,String T)
	{
		int next[]=getNext(T);
		
		int i=0,j=0;
		while(i<S.length()&&j<T.length())
		{
			if(j==-1||S.charAt(i)==T.charAt(j))
			{
				i++;j++;
			}else {
				j=next[j];
			}
		}
		
		if(j==T.length())
		{
			return (i-j);
		}
		
		return -1;
	}
	
	static void kmpall(String S,String T)
	{
		int next[]=getNext(T);
		
		int i=0,j=0;
		while(i<S.length())
		{
			if(j==-1||S.charAt(i)==T.charAt(j))
			{
				i++;j++;
			}else {
				j=next[j];
			}
			if(j==T.length())
			{
				System.out.println(i-j);
				j=0;
			}
		}
		
		
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		//System.out.println(kmp("abcdabd","ab"));
		kmpall("abcdabd","ab");
	}

}
